from tools_algorithm import *


class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        n = len(nums)

        def f(s):
            l, r = 0, 0
            cnt = Counter()
            ans = 0
            while r < n:
                cnt[nums[r]] += 1
                while len(cnt.keys()) > s:
                    cnt[nums[l]] -= 1
                    if cnt[nums[l]] == 0:
                        cnt.pop(nums[l])
                    l += 1
                ans += r - l + 1
                r += 1
            return ans

        return bisect_left(
            range((1 + n) * n // 2 + 1), ((1 + n) * n // 2 + 1) // 2, key=lambda a: f(a)
        )


s = Solution()
print(s.medianOfUniquenessArray([88, 68, 68, 88, 68]))
